package com.algorithm.sort.heap;

import java.util.*;

/**
 * leetcode-295:查找数据流的中位数
 * 采用插入排序实现
 *
 * @program: sudy
 * @className: MedianFinder
 * @description: TODO
 * @author: kukuxiahuni
 * @create: 2020-02-05 19:50
 **/
public class MedianFinder2 {

    /**
     * 数据存储列表
     */
    private List<Integer> dataList = new LinkedList<>();

    public static void main(String[] args) {
        MedianFinder2 medianFinder = new MedianFinder2();
        medianFinder.addNum(-1);
        medianFinder.addNum(-2);
        medianFinder.addNum(-3);
//        medianFinder.addNum(4);
//        medianFinder.addNum(6);

//        medianFinder.minHeap.add(1);
//        medianFinder.minHeap.add(2);
//        medianFinder.minHeap.add(3);
//        System.out.println(medianFinder.minHeap.peek());
//        medianFinder.maxHeap.add(1);
//        medianFinder.maxHeap.add(2);
//        medianFinder.maxHeap.add(3);
//        System.out.println(medianFinder.maxHeap.peek());
//        System.out.println(medianFinder.findMedian());
        System.out.println(medianFinder.findMedian());
    }

    public MedianFinder2() {

    }

    /**
     * 添加元素
     *
     * @method:
     * @param:
     * @return:
     * @author: kukuxiahuni
     * @create: 2020/2/5 21:01
     * @modify_user:TODO
     * @modify_time: 2020/2/5 21:01
     **/
    public void addNum(int num) {
        dataList.add(num);
    }

    public double findMedian() {

        Collections.sort(this.dataList);

        if (this.dataList.size() % 2 == 0) {
            return (this.dataList.get(this.dataList.size() / 2) + this.dataList.get(this.dataList.size() / 2 + 1)) / 2.0;
        } else {
            return this.dataList.get(this.dataList.size() / 2);
        }

    }

}
